package com.yanceysong.codetop.s1_s10;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName S1_Mid_146_LRU缓存
 * @Description
 * @date 2024/6/5 下午3:36
 * @Author yanceysong
 * @Version 1.0
 */
public class S2_Mid_146_LRU缓存机制 {
    /**
     * 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
     * 实现 LRUCache 类：
     * LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
     * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
     * void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
     * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
     * <p>
     * 示例：
     * <p>
     * 输入
     * ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
     * [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
     * 输出
     * [null, null, null, 1, null, -1, null, -1, 3, 4]
     * <p>
     * 解释
     * LRUCache lRUCache = new LRUCache(2);
     * lRUCache.put(1, 1); // 缓存是 {1=1}
     * lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
     * lRUCache.get(1);    // 返回 1
     * lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
     * lRUCache.get(2);    // 返回 -1 (未找到)
     * lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
     * lRUCache.get(1);    // 返回 -1 (未找到)
     * lRUCache.get(3);    // 返回 3
     * lRUCache.get(4);    // 返回 4
     * <p>
     * <p>
     * 提示：
     * <p>
     * 1 <= capacity <= 3000
     * 0 <= key <= 10000
     * 0 <= value <= 105
     * 最多调用 2 * 105 次 get 和 put
     */
    public class LRUCache {
        // 双向链表节点（Doubly Linked Node）
        class DLinkedNode {
            int key;
            int value;
            DLinkedNode prev;
            DLinkedNode next;

            public DLinkedNode() {
            }

            public DLinkedNode(int _key, int _value) {
                key = _key;
                value = _value;
            }
        }

        private final Map<Integer, DLinkedNode> cache = new HashMap<>();
        private int size;
        private final int capacity;
        private final DLinkedNode head;
        private final DLinkedNode tail;

        /**
         * LRU缓存构造函数
         * <p>
         * 初始化后的链表结构：
         * head ←→ tail
         * <p>
         * 说明：
         * - head和tail是伪节点，不存储实际数据
         * - 真实数据节点总是在head和tail之间
         * - 越靠近head的节点越"新"（最近使用）
         * - 越靠近tail的节点越"旧"（最久未使用）
         */
        public LRUCache(int capacity) {
            this.size = 0;
            this.capacity = capacity;
            // 使用伪头部和伪尾部节点，简化边界处理
            head = new DLinkedNode();
            tail = new DLinkedNode();
            head.next = tail;    // 初始状态：head → tail
            tail.prev = head;    // 初始状态：head ← tail
        }

        public int get(int key) {
            DLinkedNode node = cache.get(key);
            if (node == null) {
                return -1;
            }
            // 如果 key 存在，先通过哈希表定位，再移到头部
            moveToHead(node);
            return node.value;
        }

        public void put(int key, int value) {
            DLinkedNode node = cache.get(key);
            if (node == null) {
                // 如果 key 不存在，创建一个新的节点
                DLinkedNode newNode = new DLinkedNode(key, value);
                // 添加进哈希表
                cache.put(key, newNode);
                // 添加至双向链表的头部
                addToHead(newNode);
                ++size;
                if (size > capacity) {
                    // 如果超出容量，删除双向链表的尾部节点
                    DLinkedNode tail = removeTail();
                    // 删除哈希表中对应的项
                    cache.remove(tail.key);
                    --size;
                }
            } else {
                // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
                node.value = value;
                moveToHead(node);
            }
        }

        /**
         * 将节点添加到链表头部（紧跟在伪头节点后面）
         * <p>
         * 操作前链表结构：
         * head ←→ nodeA ←→ nodeB ←→ ... ←→ tail
         * <p>
         * 操作后链表结构：
         * head ←→ node ←→ nodeA ←→ nodeB ←→ ... ←→ tail
         * <p>
         * 步骤详解：
         * 1. node.prev = head           : node ← head
         * 2. node.next = head.next      : node → nodeA
         * 3. head.next.prev = node      : node ← nodeA
         * 4. head.next = node           : head → node
         * <p>
         * 最终形成：head ←→ node ←→ nodeA ←→ nodeB ←→ ... ←→ tail
         */
        private void addToHead(DLinkedNode node) {
            node.prev = head;           // 步骤1: 设置新节点的前驱为head
            node.next = head.next;      // 步骤2: 设置新节点的后继为原来的第一个节点
            head.next.prev = node;      // 步骤3: 原来第一个节点的前驱指向新节点
            head.next = node;           // 步骤4: head的后继指向新节点
        }

        /**
         * 从链表中移除指定节点
         * <p>
         * 操作前链表结构：
         * ... ←→ prevNode ←→ node ←→ nextNode ←→ ...
         * <p>
         * 操作后链表结构：
         * ... ←→ prevNode ←→ nextNode ←→ ...
         * <p>
         * 步骤详解：
         * 1. node.prev.next = node.next  : prevNode → nextNode (跳过node)
         * 2. node.next.prev = node.prev  : prevNode ← nextNode (跳过node)
         * <p>
         * 注意：node节点被孤立，但其prev和next指针仍指向原位置
         * 这不影响功能，因为HashMap中的引用会被更新或删除
         */
        private void removeNode(DLinkedNode node) {
            node.prev.next = node.next;  // 步骤1: 前驱节点跳过当前节点，直接指向后继
            node.next.prev = node.prev;  // 步骤2: 后继节点跳过当前节点，直接指向前驱
        }

        /**
         * 将节点移动到链表头部（表示最近使用）
         * <p>
         * 操作前链表结构（假设node在中间位置）：
         * head ←→ nodeA ←→ nodeB ←→ node ←→ nodeC ←→ tail
         * <p>
         * 第一步：removeNode(node) - 从当前位置移除
         * head ←→ nodeA ←→ nodeB ←→ nodeC ←→ tail
         * ↑
         * node (孤立)
         * <p>
         * 第二步：addToHead(node) - 添加到头部
         * head ←→ node ←→ nodeA ←→ nodeB ←→ nodeC ←→ tail
         * <p>
         * 最终效果：node从原位置移动到了最前面，表示它是最近访问的
         * <p>
         * 使用场景：
         * - get操作时，将访问的节点标记为最近使用
         * - put操作更新已存在key时，将节点标记为最近使用
         */
        private void moveToHead(DLinkedNode node) {
            removeNode(node);    // 第一步：从当前位置移除节点
            addToHead(node);     // 第二步：将节点添加到头部
        }

        /**
         * 移除链表尾部节点（最久未使用的节点）
         * <p>
         * 操作前链表结构：
         * head ←→ nodeA ←→ nodeB ←→ nodeC ←→ lastNode ←→ tail
         * ↑
         * 最久未使用
         * <p>
         * 第一步：找到最后一个真实节点
         * DLinkedNode res = tail.prev;  // res指向lastNode
         * <p>
         * 第二步：removeNode(res) - 移除最后一个节点
         * head ←→ nodeA ←→ nodeB ←→ nodeC ←→ tail
         * ↑
         * lastNode (孤立)
         * <p>
         * 操作后链表结构：
         * head ←→ nodeA ←→ nodeB ←→ nodeC ←→ tail
         * <p>
         * 返回值：被移除的lastNode，调用者需要从HashMap中删除对应的key
         * <p>
         * 使用场景：
         * - 当缓存容量超限时，淘汰最久未使用的元素
         * - 总是移除tail.prev节点（伪尾节点的前一个节点）
         */
        private DLinkedNode removeTail() {
            DLinkedNode res = tail.prev;  // 第一步：获取最后一个真实节点（最久未使用）
            removeNode(res);              // 第二步：从链表中移除该节点
            return res;                   // 第三步：返回被移除的节点，用于从HashMap中删除
        }
    }

    public static void main(String[] args) {
        S2_Mid_146_LRU缓存机制 solution = new S2_Mid_146_LRU缓存机制();

        System.out.println("=== LRU缓存测试开始 ===");

        // 测试1: 基本功能测试 - 题目示例
        System.out.println("\n--- 测试1: 基本功能测试 (题目示例) ---");
        testBasicExample(solution);

        // 测试2: 容量为1的边界情况
        System.out.println("\n--- 测试2: 容量为1的边界情况 ---");
        testCapacityOne(solution);

        // 测试3: 更新已存在的key
        System.out.println("\n--- 测试3: 更新已存在的key ---");
        testUpdateExistingKey(solution);

        // 测试4: 访问顺序影响LRU
        System.out.println("\n--- 测试4: 访问顺序影响LRU ---");
        testAccessOrder(solution);

        // 测试5: 大容量测试
        System.out.println("\n--- 测试5: 大容量测试 ---");
        testLargeCapacity(solution);

        // 测试6: 边界值测试
        System.out.println("\n--- 测试6: 边界值测试 ---");
        testBoundaryValues(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 测试基本功能 - 题目给出的示例
     */
    private static void testBasicExample(S2_Mid_146_LRU缓存机制 solution) {
        LRUCache lRUCache = solution.new LRUCache(2);

        System.out.println("创建容量为2的LRU缓存");

        lRUCache.put(1, 1);
        System.out.println("put(1, 1) -> 缓存: {1=1}");

        lRUCache.put(2, 2);
        System.out.println("put(2, 2) -> 缓存: {1=1, 2=2}");

        int result1 = lRUCache.get(1);
        System.out.println("get(1) -> " + result1 + " (期望: 1)");
        assert result1 == 1 : "get(1)应该返回1";

        lRUCache.put(3, 3);
        System.out.println("put(3, 3) -> 缓存: {1=1, 3=3} (淘汰key=2)");

        int result2 = lRUCache.get(2);
        System.out.println("get(2) -> " + result2 + " (期望: -1)");
        assert result2 == -1 : "get(2)应该返回-1";

        lRUCache.put(4, 4);
        System.out.println("put(4, 4) -> 缓存: {3=3, 4=4} (淘汰key=1)");

        int result3 = lRUCache.get(1);
        System.out.println("get(1) -> " + result3 + " (期望: -1)");
        assert result3 == -1 : "get(1)应该返回-1";

        int result4 = lRUCache.get(3);
        System.out.println("get(3) -> " + result4 + " (期望: 3)");
        assert result4 == 3 : "get(3)应该返回3";

        int result5 = lRUCache.get(4);
        System.out.println("get(4) -> " + result5 + " (期望: 4)");
        assert result5 == 4 : "get(4)应该返回4";

        System.out.println("✓ 基本功能测试通过");
    }

    /**
     * 测试容量为1的边界情况
     */
    private static void testCapacityOne(S2_Mid_146_LRU缓存机制 solution) {
        LRUCache cache = solution.new LRUCache(1);

        System.out.println("创建容量为1的LRU缓存");

        cache.put(1, 10);
        System.out.println("put(1, 10)");

        int result1 = cache.get(1);
        System.out.println("get(1) -> " + result1 + " (期望: 10)");
        assert result1 == 10 : "get(1)应该返回10";

        cache.put(2, 20);
        System.out.println("put(2, 20) -> 淘汰key=1");

        int result2 = cache.get(1);
        System.out.println("get(1) -> " + result2 + " (期望: -1)");
        assert result2 == -1 : "get(1)应该返回-1";

        int result3 = cache.get(2);
        System.out.println("get(2) -> " + result3 + " (期望: 20)");
        assert result3 == 20 : "get(2)应该返回20";

        System.out.println("✓ 容量为1测试通过");
    }

    /**
     * 测试更新已存在的key
     */
    private static void testUpdateExistingKey(S2_Mid_146_LRU缓存机制 solution) {
        LRUCache cache = solution.new LRUCache(2);

        System.out.println("创建容量为2的LRU缓存");

        cache.put(1, 10);
        cache.put(2, 20);
        System.out.println("put(1, 10), put(2, 20)");

        cache.put(1, 100);  // 更新key=1的值
        System.out.println("put(1, 100) -> 更新key=1的值并移到最前");

        int result1 = cache.get(1);
        System.out.println("get(1) -> " + result1 + " (期望: 100)");
        assert result1 == 100 : "get(1)应该返回100";

        cache.put(3, 30);  // 应该淘汰key=2
        System.out.println("put(3, 30) -> 应该淘汰key=2");

        int result2 = cache.get(2);
        System.out.println("get(2) -> " + result2 + " (期望: -1)");
        assert result2 == -1 : "get(2)应该返回-1";

        int result3 = cache.get(1);
        System.out.println("get(1) -> " + result3 + " (期望: 100)");
        assert result3 == 100 : "get(1)应该返回100";

        System.out.println("✓ 更新已存在key测试通过");
    }

    /**
     * 测试访问顺序对LRU的影响
     */
    private static void testAccessOrder(S2_Mid_146_LRU缓存机制 solution) {
        LRUCache cache = solution.new LRUCache(3);

        System.out.println("创建容量为3的LRU缓存");

        cache.put(1, 10);
        cache.put(2, 20);
        cache.put(3, 30);
        System.out.println("put(1, 10), put(2, 20), put(3, 30)");

        // 访问key=1，使其变为最近使用
        cache.get(1);
        System.out.println("get(1) -> 使key=1变为最近使用");

        // 访问key=2，使其变为最近使用
        cache.get(2);
        System.out.println("get(2) -> 使key=2变为最近使用");

        // 添加新元素，应该淘汰key=3（最久未使用）
        cache.put(4, 40);
        System.out.println("put(4, 40) -> 应该淘汰key=3");

        int result1 = cache.get(3);
        System.out.println("get(3) -> " + result1 + " (期望: -1)");
        assert result1 == -1 : "get(3)应该返回-1";

        int result2 = cache.get(1);
        System.out.println("get(1) -> " + result2 + " (期望: 10)");
        assert result2 == 10 : "get(1)应该返回10";

        int result3 = cache.get(2);
        System.out.println("get(2) -> " + result3 + " (期望: 20)");
        assert result3 == 20 : "get(2)应该返回20";

        int result4 = cache.get(4);
        System.out.println("get(4) -> " + result4 + " (期望: 40)");
        assert result4 == 40 : "get(4)应该返回40";

        System.out.println("✓ 访问顺序测试通过");
    }

    /**
     * 测试大容量
     */
    private static void testLargeCapacity(S2_Mid_146_LRU缓存机制 solution) {
        LRUCache cache = solution.new LRUCache(100);

        System.out.println("创建容量为100的LRU缓存");

        // 添加100个元素
        for (int i = 1; i <= 100; i++) {
            cache.put(i, i * 10);
        }
        System.out.println("添加100个元素 (1->10, 2->20, ..., 100->1000)");

        // 验证所有元素都存在
        for (int i = 1; i <= 100; i++) {
            int result = cache.get(i);
            assert result == i * 10 : "get(" + i + ")应该返回" + (i * 10);
        }
        System.out.println("验证所有100个元素都能正确获取");

        // 添加第101个元素，应该淘汰第1个元素
        cache.put(101, 1010);
        System.out.println("put(101, 1010) -> 应该淘汰key=1");

        int result1 = cache.get(1);
        System.out.println("get(1) -> " + result1 + " (期望: -1)");
        assert result1 == -1 : "get(1)应该返回-1";

        int result101 = cache.get(101);
        System.out.println("get(101) -> " + result101 + " (期望: 1010)");
        assert result101 == 1010 : "get(101)应该返回1010";

        System.out.println("✓ 大容量测试通过");
    }

    /**
     * 测试边界值
     */
    private static void testBoundaryValues(S2_Mid_146_LRU缓存机制 solution) {
        LRUCache cache = solution.new LRUCache(2);

        System.out.println("创建容量为2的LRU缓存，测试边界值");

        // 测试key和value的边界值
        cache.put(0, 0);  // 最小key和value
        cache.put(10000, 100000);  // 最大key和较大value
        System.out.println("put(0, 0), put(10000, 100000)");

        int result1 = cache.get(0);
        System.out.println("get(0) -> " + result1 + " (期望: 0)");
        assert result1 == 0 : "get(0)应该返回0";

        int result2 = cache.get(10000);
        System.out.println("get(10000) -> " + result2 + " (期望: 100000)");
        assert result2 == 100000 : "get(10000)应该返回100000";

        // 测试不存在的key
        int result3 = cache.get(5000);
        System.out.println("get(5000) -> " + result3 + " (期望: -1, key不存在)");
        assert result3 == -1 : "get(5000)应该返回-1";

        // 测试相同key的多次put
        cache.put(0, 999);
        cache.put(0, 888);
        cache.put(0, 777);
        System.out.println("多次put(0, value)，最终value=777");

        int result4 = cache.get(0);
        System.out.println("get(0) -> " + result4 + " (期望: 777)");
        assert result4 == 777 : "get(0)应该返回777";

        System.out.println("✓ 边界值测试通过");
    }
}